Many images used on the world wide web are graphic images, as opposed to natural or photographic images of real images. Graphic images are generally images created by people with the assistance of computer tools. Examples of images are menus (including various types of listings), explanatory diagrams, maps, comics and cartoons, and images of documents and graphic drawings. Graphic images typically have very different data compression characteristics from natural and photographic images. While the present invention can be used with natural and photographic images, its benefits are believed to be strongest when used with graphic images. The terms “non-graphic image” and natural image are often used synonymously, even though non-graphic images may be computer generated or manmade in part or in whole. Non-graphic images, as that term is used in this document, generally include full color information (three color components are explicitly specified) for each pixel, and thus are not restricted to the colors in a color palette, such as a 256 color palette or a 1024 color palette.
A graphic image is defined for the purposes of this document to mean an image whose pixels have no more than 1024 distinct colors, and thus can be represented using relatively small palette-based pixel values.
Images are digitally encoded using a number of well known encoding methods. Some of the best known digital image encoding formats are GIF (graphic image format), PNG (portable networks graphics), BMP (bit map), PCX (PC paintbrush family, a fixed length encoding method), JPEG, various proprietary encodings, and various wavelet-based and wavelet-like-based encodings. A fairly complete listing of digital image encoding formats can be found at http://www.dcs.ed.ac.uk/home/mxr/gfx/2d-hi.html (The Graphics File Formats Page), and descriptions of these graphics encoding methods and formats can be found in many graphics textbooks, as well as in documents referenced by the aforementioned “The Graphics File Formats Page”.
The present invention primarily concerns the encoding, decoding, transmission and management of bitmapped graphic image data, raster scanned graphic images, and run-length encoded and pattern encoded” images, which include images encoded using GIF, PNG and PCX. For the purposes of this document, the term “run length encoded” images is defined to include both traditional run length encodings of images, such as PCX encoded images, as well as “pattern encoded” images, such as GIF encoded images.
GIF and PNG are popular file formats for encoding images that are “palette based,” but which present significant problems when downloading to bandwidth limited wireless devices having small display screens. Such devices typically can display only a small portion of a graphic image at any one time, because of the limited size of their displays, and also have limited memory for storing a downloaded image, making it impossible for many such devices to store large digital images. Also, the limited communication bandwidth of such devices, often just ten to fifty thousand bits per second, means that it would take several minutes or even longer to download many of the images that are routinely transmitted over the world wide web to desktop computers.
“Palette-based” images are images where the color of each pixel of the image is represented as an index or position in a specified color palette. For instance, many graphic images are digitally encoded using a 256 color palette, and each pixel of such an image is encoded as one of those 256 colors. Since it takes 8 bits to represent a selection of one of 256 colors, a very simple encoding would be to represent each pixel as an 8-bit index into the 256 color palette. A more sophisticated encoding method is to pair with an palette index a “run length value,” where the run length value indicates the number of consecutive pixels in the image that all have the same color. “Consecutive pixels” are usually defined with respect to a raster scan of the image, and usually means a contiguous set of pixels on the same horizontal scan line. A next level of sophistication uses a lossless data compression method known as Lempel-Zif. The GIF and PNG graphic image formats use specific versions of the Lempel-Zif method. Since the actual encoding methods used in GIF, PNG and PCX are a matter of public record, a complete explanation of these encoding methods is not provided here.
Due to the manner in which GIF and PNG images are encoded, it is not possible to send a device just a small portion of the GIF image (other than the top portion of the image). Rather, the entire image file must be downloaded and processed to reproduce an arbitrarily selected portion of the image. For instance, if an image is 640×832 pixels, and the device in question has a display region of 64×64 pixels, the device can display at any one time less than 1% of the image. Downloading the entire 640×832 pixel image to the device via a wireless connection will take approximately 130 times as long as it would ideally take to download only the portion of the image to be viewed. Of course this assumes that small 64×64 images can be encoded as efficiently as the 640×832 image, which is generally not the case, but even if the encoding of the 64×64 image were only half as efficient as the encoding of the larger image, the transmission time of the larger image would still be about 65 times as long as the transmission time of the smaller image.
The present invention provides a highly efficient system, method and computer program product for encoding and re-encoding palette-based graphic images, in small portions called blocks, to enable portions of such images to be efficiently downloaded from a server to various devices for viewing. The present invention minimizes or reduces the encoding efficiency “penalty” incurred by using small images, herein called blocks, while at the same time providing a mechanism for enabling small images to be downloaded to wireless and other bandwidth limited devices very quickly.